\input{euler.tex}

\begin{document}

\problem[303]{Multiples With Small Digits}

For a positive integer $n$, define $f(n)$ as the smallest positive multiple of $n$ that, written in base 10, uses only digits $\le 2$.

For example, $f(2)=2$, $f(3)=12$, $f(7)=21$, $f(42)=210$, $f(89)=1121222$. Also, $\sum_{n=1}^{100} f(n)/n = 11363107$.
 
Find $\sum_{n=1}^{10000} f(n)/n$. 

\solution

We generalize the problem a little bit, and try to find the smallest multiplier $m = m(n; c)$ such that
\[
n \times m + c = a_k \times 10^k + \cdots + a_1 \times 10 + a_0
\]
only uses digits 0, 1, or 2. Here $0 \le c < n$ is some given integer. The problem in question is just the special case where $c=0$.

We start by examining possible choices for the lowest digit of $m$. Let $m = 10 m' + d$ and substitute it into the above equation, we get
\[
n \times (10 m'+d) + c = (a_k \times 10^{k-1} + \cdots + a_1 ) \times 10 + a_0
\]
which yields
\[
nd + c \equiv a_0 = 0, 1, 2 \mod 10 .
\]
From this equation we can find a few $d$s that satisfy the condition.

For a given $d$, we can eliminate the lowest digit and consider the remaining more significant digits. This gives
\[
n \times m' + \lfloor (nd+c)/10 \rfloor = a_k \times 10^{k-1} + \cdots + a_1 .
\]
Note that $(nd+c)/10 < (9n+n)/10 = n$, so we can denote $c' = \lfloor (nd+c)/10 \rfloor$, and turn the equation into the same form as before. Hence, 
\[
m(n; c) = \min_d m(n; \lfloor (nd+c)/10 \rfloor) \times 10 + d .
\]

We use a breadth-first-search approach to find the solution. Start with $m(n; 0)$, and expand its children corresponding to allowable lowest digits. Each child corresponds to a difference $c$ (carry), and there are no more than 10 children to expand for each parent node. For each child, record the multiplier that achieves this carry. Repeat this process recursively. If a child is already expanded, we just need to update its multiplier (if smaller) and no need to expand again. 

One minor optimization that could be done is to note that if $f(n) = m \times n$, then for any of $m$'s divisors, $d$, $f(nd) = (m/d) \times n$. This saves us some work when we need to sum up $f(n)$ over a range, but is not useful in computing any particular $f(n)$.

\answer

1111981904675169

\complexity

Time complexity: $\BigO(n^2)$

Space complexity: $\BigO(n)$

\end{document} 